/*
Todo
1. 编写链栈的进栈、出栈、显示栈中全部元素的程序。
2. 将一个正整数n转换成R进制，要求用顺序栈的来实现。
3. 用switch语句设计一个选择式菜单，以菜单方式执行上述操作。
*/

#include <stdlib.h>
#include "stdio.h"

typedef int datatype;
typedef struct node   //定义链式栈结构
{
    datatype data;
    struct node *next;
} StackNode, *LinkStack;

//初始化栈
LinkStack Init_LinkStack() {
    LinkStack top;
    top = (StackNode *) malloc(sizeof(StackNode));
    top->next = NULL;
    return top;
}

//入栈
int Push_LinkStack(LinkStack top, datatype x) {
    LinkStack p;
    p = (StackNode *) malloc(sizeof(StackNode));
    p->data = x;
    p->next = top->next;
    top->next = p;
    return 1;
}

//出栈
datatype *Pop_LinkStack(LinkStack top, datatype *x) {
    LinkStack p;
    p = top->next;
    top->next = p->next;
    *x = p->next;
    *x = p->data;
    free(p);
    return x;
}

void print(LinkStack top) {
    LinkStack p = top;
    while (p != NULL) {
        printf("%d->", p->data);
        p = p->next;
    }
}

#define MAXSIZE  1024
typedef struct {
    datatype data[MAXSIZE];
    int top;
} SeqStack;

//顺序栈置空栈：首先建立栈空间，然后初始化栈顶指针。
SeqStack *Init_SeqStack() {
    SeqStack *s;
    s = (SeqStack *) malloc(sizeof(SeqStack));
    s->top = -1;
    return s;
}

//顺序栈判空栈
int Empty_SeqStack(SeqStack *s) {
    if (s->top == -1) return 1;
    else return 0;
}

//顺序栈入栈
int Push_SeqStack(SeqStack *s, datatype x) {
    if (s->top == MAXSIZE - 1) return 0; //栈满不能入栈
    else {
        s->top++;
        s->data[s->top] = x;
        return 1;
    }
}

//顺序栈出栈
int Pop_SeqStack(SeqStack *s, datatype *x) {
    if (Empty_SeqStack(s)) return 0; //栈空不能出栈
    else {
        *x = s->data[s->top];
        s->top--;
        return 1;        //栈顶元素存入*x，返回
    }
}

void conversion(int N, int r) {
    SeqStack *s;
    datatype x;
    s = Init_SeqStack();        //初始化栈
    while (N != 0) {
        Push_SeqStack(s, N % r);     //余数入栈
        N = N / r;                //商作为被除数继续
    }
    while (!Empty_SeqStack(s)) {
        Pop_SeqStack(s, &x);
        printf(" %d ", x);
    }
}


int main() {
    LinkStack top;
    top = Init_LinkStack();
    int i, j, k;
    datatype x;
    do {
        printf("\n\n\n\n");
        printf("\t\t\t 栈的应用子系统\n");
        printf("\t\t*******************************\n");
        printf("\t\t*        1----链式进栈　  　　*\n");
        printf("\t\t*        2----链式出栈　　　　*\n");
        printf("\t\t*        3----链栈显示　　　　*\n");
        printf("\t\t*        4----进制转换　　　　*\n");
        printf("\t\t*        0----返　　回　　　　*\n");
        printf("\t\t*******************************\n");
        printf("\t\t 请选择菜单项(0－4)：");
        scanf("%d", &k);
        getchar();
        switch (k) {
            case 1:         //进栈
                printf("\n   请输入要进栈的数据X:");
                scanf("%d", &x);
                getchar();
                Push_LinkStack(top, x);
                break;
            case 2:         //出栈
                printf("---出栈--- \n");
                datatype value;
                datatype *res;
                res = Pop_LinkStack(top, &value);
                printf("%d", *res);
                break;
            case 3:
//                打印栈
                print(top);
                break;
            case 4:
                printf("进制转换");
                int N, r;
                printf("\n,请输入一个整数N=");
                scanf("%d", &N);
                getchar();
                printf("\n,请输入一个要转换的进制数r=");
                scanf("%d", &r);
                getchar();
                conversion(N, r);

        }
    } while (k != 0);
    return 0;
}